package com.company.chu;

public class Sort2 {

    public static void main(String[] args) {
        int[] nums = {3,4,5,6,1,7,8,9};
        System.out.println("排序前的数组");
        for (int i:nums) System.out.print(i);
        System.out.println();
//        insertSort(nums);
//        System.out.println("插入排序后的数组");
//        for (int i:nums) System.out.print(i);
        quickSort(nums,0,nums.length-1);
        System.out.println("排序后的数组");
        for (int i:nums) System.out.print(i);
    }



    static void insertSort(int[] nums){
        int len  = nums.length;
        for (int i = 1;i<len;i++){
            int j = i-1;
            int value = nums[i];
            for (;j>=0;j--){
                if(nums[j]>value){
                    nums[j+1] = nums[j];
                }else {
                    break;
                }
            }
            nums[j+1] = value;
        }
    }


    static void quickSort(int[] nums,int low,int high){
        // 主要思路就是确定一个基准点
        if(low>high){
            return;
        }
        int temp = nums[low];
        int i = low ,j = high;
        while (i<j){
            while (i<j && nums[j] >=temp){
                j--;
            }
            while (i<j && nums[i]<= temp){
                i++;
            }
            if(i <j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        nums[low] = nums[i];
        nums[i] = temp;
        quickSort(nums,low,i-1);
        quickSort(nums,i+1,high);
    }
}
